package com.wenhao.leetcode.medium;

/**
 * 题目：https://leetcode-cn.com/problems/search-a-2d-matrix/
 * 搜索二维矩阵
 *
 * 这一题和剑指offer上面的不一样，整个矩阵是递增的，所以可以优化到log(mn)
 * @author Wenhao Tong
 * @create 2021-07-12 12:55
 */
public class LeetCode74 {
    public static void main(String[] args) {

    }

    public boolean searchMatrix2(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int lo = 0;
        int hi = m * n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (target == matrix[mid / n][mid % n]) {
                return true;
            }
            if (target < matrix[mid / n][mid % n]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return false;
    }


    public boolean searchMatrix(int[][] matrix, int target) {
        int top = 0;
        int right = matrix[0].length - 1;
        while (top < matrix.length && right > -1) {
            if (matrix[top][right] == target) {
                return true;
            }
            if (matrix[top][right] > target) {
                right--;
            }
            if (right > -1 && matrix[top][right] < target) {
                top++;
            }
        }
        return false;
    }
}
